In this paper, we study grid-obstacle representations of graphs where weassign grid-points to vertices and define obstacles such that an edge exists ifand only if an $xy$-monotone grid path connects the two endpoints withouthitting an obstacle or another vertex. It was previously argued that all planargraphs have a grid-obstacle representation in 2D, and all graphs have agrid-obstacle representation in 3D. In this paper, we show that suchconstructions are possible with significantly smaller grid-size than previouslyachieved. Then we study the variant where vertices are not blocking, and showthat then grid-obstacle representations exist for bipartite graphs. The latterhas applications in so-called staircase guarding of orthogonal polygons; usingour grid-obstacle representations, we show that staircase guarding is\textsc{NP}-hard in 2D.
展开▼
